package algorithm;

import java.util.Stack;

/**
 * @author apple
 * @Classname DepthFirstSearch
 * @Description 深度优先遍历
 * @Date 2020/4/18 14:21
 */
public class DepthFirstSearch {

    /**
     * 深度优先遍历 递归方式
     **/
    public static void dfs(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        System.out.println(treeNode.value);
        /**遍历左子节点**/
        dfs(treeNode.leftTreeNode);
        /**遍历右子节点**/
        dfs(treeNode.rightTreeNode);
    }

    /**
     * 深度优先遍历 非递归实现，使用栈实现
     **/
    public static void dfsWithStack(TreeNode rootNode) {
        if (rootNode == null) {
            return;
        }
        /**初始化栈**/
        Stack<TreeNode> stack = new Stack<>();
        /**首先根节点压栈**/
        stack.push(rootNode);
        /**栈非空时遍历**/
        while (!stack.isEmpty()) {
            TreeNode treeNode = stack.pop();
            /**遍历节点**/
            System.out.println(treeNode.value);
            /**非空右节点先压栈**/
            if (treeNode.rightTreeNode != null) {
                stack.push(treeNode.rightTreeNode);
            }
            /**非空左节点压栈**/
            if (treeNode.leftTreeNode != null) {
                stack.push(treeNode.leftTreeNode);
            }
        }
    }

    /**二叉树的最大深度**/
    public static int getMaxDepth(TreeNode treeNode){
        if(treeNode == null){
            return 0;
        }
        int leftMaxDepth=getMaxDepth(treeNode.leftTreeNode)+1;
        int rightMaxDepth=getMaxDepth(treeNode.rightTreeNode)+1;
        return Math.max(leftMaxDepth,rightMaxDepth);
    }

    /**二叉树的最小深度**/
    public static int getMinDepth(TreeNode treeNode){
        if(treeNode == null){
            return 0;
        }
        int leftMinDepth=getMinDepth(treeNode.leftTreeNode)+1;
        int rightMinDepth=getMinDepth(treeNode.rightTreeNode)+1;
        return Math.min(leftMinDepth,rightMinDepth);
    }
    public static void main(String[] args) {
        int[] list = {10, 25, 13, 1, 6, 11, 15};
        BinaryTree binaryTree =BinaryTreeBuilder.createBinaryTree(list);
        /**递归实现**/
        System.out.println("递归实现");
        dfs(binaryTree.getRoot());
        /**非递归实现，栈实现**/
        System.out.println("非递归实现，栈实现");
        dfsWithStack(binaryTree.getRoot());

        /**二叉树的最大深度**/
        System.out.println("二叉树的最大深度");
        System.out.println(getMaxDepth(binaryTree.getRoot()));
        /**二叉树的最小深度**/
        System.out.println("二叉树的最小深度");
        System.out.println(getMinDepth(binaryTree.getRoot()));
    }

}
